import java.util.*;

public class MST
{

    /**
     * Using Disjoint set(s), run Kruskal's algorithm on the given graph and return the MST, return
     * null if no MST exists for the graph
     * 
     * @param g
     *            The graph, g will never be null
     * @return the MST of the graph, null if no valid MST exists
     */
    public static Collection<Edge> kruskals(Graph g)
    {
        ArrayList<Edge> mst = new ArrayList<Edge>();
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>(g.getEdgeList());
        DisjointSets<Vertex> disjointSets = new DisjointSets<Vertex>(g.getVertices());
        int stoppingPoint = g.getVertices().size() - 1; //stop adding edges if the number of edges is equal to V-1
        while(priorityQueue.size() != 0 && mst.size() < stoppingPoint)
        {
            Edge e = priorityQueue.poll();
            if(!disjointSets.sameSet(e.getU(),e.getV()))
            {
                disjointSets.merge(e.getU(),e.getV());
                mst.add(e);
            }
        }
        //check to see if valid mst
        if(!disjointSets.isMerged())
        {
            return null;
        }
        return mst;
    }

    /**
     * Run Prim's algorithm on the given graph and return the minimum spanning tree
     * If no MST exists, return null
     * 
     * @param g 
     * 				The graph to be processed.  Will never be null
     * @param start 
     * 				The ID of the start node.  Will always exist in the graph
     * @return the MST of the graph, null if no valid MST exists
     */
    public static Collection<Edge> prims(Graph g, int start)
    {
        ArrayList<Vertex> visitedList = new ArrayList<Vertex>();
        ArrayList<Edge> mst = new ArrayList<Edge>();
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        int size = g.getVertices().size()-1;

        //add adjacent edges of start to pq
        Vertex starting = new Vertex(start);
        Map<Vertex, Integer> adjacent = g.getAdjacencies(starting);
        Iterator it = adjacent.entrySet().iterator();
        while (it.hasNext())
        {
            Map.Entry pairs = (Map.Entry)it.next();
            priorityQueue.add(new Edge(starting, (Vertex)pairs.getKey(), (int)pairs.getValue()));
            it.remove();
        }
        visitedList.add(starting);

        while(visitedList.size() < size)
        {
            if(priorityQueue.isEmpty())
            {
                return null;
            }
            Edge current = priorityQueue.poll(); //poll from pq
            if(!visitedList.contains(current.getU()))
            {
                //add u to visited
                visitedList.add(current.getU());
                //add all its edges to the pq
                adjacent = g.getAdjacencies(current.getU());
                it = adjacent.entrySet().iterator();
                while (it.hasNext())
                {
                    Map.Entry pairs = (Map.Entry)it.next();
                    priorityQueue.add(new Edge(current.getU(), (Vertex)pairs.getKey(), (int)pairs.getValue()));
                    it.remove();
                }
                mst.add(current);
            }
            else if(!visitedList.contains(current.getV()))
            {
               //add v to visited
                visitedList.add(current.getV());
               //add all its edges to pq
                adjacent = g.getAdjacencies(current.getV());
                it = adjacent.entrySet().iterator();
                while (it.hasNext())
                {
                    Map.Entry pairs = (Map.Entry)it.next();
                    priorityQueue.add(new Edge(current.getV(), (Vertex)pairs.getKey(), (int)pairs.getValue()));
                    it.remove();
                }
                mst.add(current);
            }
        }
        return mst;
    }
}